import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode createBinaryTree() {
        TreeNode A = new TreeNode(1);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(2);
        TreeNode D = new TreeNode(3);
        TreeNode E = new TreeNode(3);
        TreeNode F = new TreeNode(4);
        TreeNode G = new TreeNode(4);

        A.left = B;
        A.right = C;

        B.left = D;
        B.right = E;

        D.left = F;
        D.right = F;


        return A;
    }

    /**
     * 层序遍历
     */
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /**
     * 时间复杂度O(N^2)
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        int leftHeight = getBinaryTreeHeight(root.left);
        int rightHeight = getBinaryTreeHeight(root.right);
        if (Math.abs(leftHeight - rightHeight) < 2 && isBalanced(root.left)
                && isBalanced(root.right)) {
            return true;
        }

        return false;
    }

    public int getBinaryTreeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftHeight = getBinaryTreeHeight(root.left);
        int rightHeight = getBinaryTreeHeight(root.right);

        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 进阶版
     *
     * @param root
     * @return
     */
    public boolean isBalanced2(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftH = getBinaryTreeHeight2(root.left);
        int rightH = getBinaryTreeHeight2(root.right);
        return leftH >= 0
                && rightH >= 0 && Math.abs(leftH - rightH) < 2;
        //return getBinaryTreeHeight2(root);
    }

    public int getBinaryTreeHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftHeight = getBinaryTreeHeight2(root.left);
        int rightHeight = getBinaryTreeHeight2(root.right);

        if (leftHeight >= 0 && rightHeight >= 0
                && Math.abs(leftHeight - rightHeight) <= 1) {//不超过1,正常返回最大高度差
            return Math.max(leftHeight, rightHeight) + 1;
        } else {//如果子树存在-1,证明高度差超过1,则直接(继续)返回-1
            return -1;
        }
    }

    /**
     * 对称二叉树
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode rootLeft, TreeNode rootRight) {
        if (rootLeft == null && rootRight == null) {
            return true;
        }
        if (rootLeft == null && rootRight != null ||
                rootLeft != null && rootRight == null) {
            return false;
        }
        if (rootLeft.val != rootRight.val) {
            return false;
        }
        return isSymmetricChild(rootLeft.left, rootRight.right) &&
                isSymmetricChild(rootLeft.right, rootRight.left);
    }

    /**
     * 二叉树的层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> retList = new ArrayList<>();
        if(root == null) {
            return retList;
        }


        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();

            while(size != 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            retList.add(list);
        }
        return retList;
    }
}
